package BFS;

import java.util.*;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-03-10
 * Time:17:30
 * Text：433. 最小基因变化
 */
public class Texts2 {
    public int minMutation(String startGene, String endGene, String[] bank)
    {
        Set<String> vis=new HashSet<>();  //遍历已经搜过的字符
        Set<String> hash=new HashSet<>();  //存储基因库
        for(String s: bank) hash.add(s);

        char[] change={'A','C','G','T'};
        if(startGene.equals(endGene)) return 0;
        if(!hash.contains(endGene)) return -1;

        int ret=0;
        Queue<String> q=new LinkedList<>();
        q.add(startGene);
        vis.add(startGene);
        while(!q.isEmpty())
        {
            ret++;
            int size=q.size();
            while(size-->0)
            {
                String str2=q.poll();
                for(int i=0;i<8;i++)
                {
                    char[] str=str2.toCharArray();
                    for(int k=0;k<4;k++)
                    {
                        str[i]=change[k];
                        String next=new String(str);
                        if(!vis.contains(next) && hash.contains(next))
                        {
                            if(next.equals(endGene))
                                return ret;
                            q.add(next);
                            vis.add(next);
                        }
                    }
                }
            }

        }
        return -1;
    }
}
